Approche avec les équations de Bellman

1. Stratégie (Policy)

Dans les exemples que nous avons vus, l'objectif de l'agent a été de trouver (apprendre) des stratégies optimales lui permettant d'atteindre son but. L'agent a appris une stratégie (policy) en faisant en sorte de maximiser les gains collectés dans son environnement. L'agent, à chaque état de son environnement, doit choisir une action à effectuer parmi un ensemble d'actions disponibles.

Une stratégie peut donc être vue comme une fonction qui à un état $s$ (avec $s \in S$ où $S$ est l'espace des états) fait correspondre une action $a$ (avec $a \in A$ où $A$ est l'espace des actions).

Une stratégie (policy) est une application de l'espace des états $S$ vers l'espace des actions $A$. Elle peut être déterministe ou stochastique. Cette application est notée $\pi$ :

• Stratégie déterministe : $\pi \left( s \right) = a$
• Stratégie stochastique : $\pi \left( {a|s} \right) = {P_\pi }\left[ {A = a|S = s} \right]$

2. Fonction valeur d'état (State value function)

Lorsque l'agent apprend une stratégie, une chose essentielle pour lui est de pouvoir évaluer la valeur d'un état (state value). Cette valeur quantifie l'importance pour un agent d'être dans cet état en suivant la stratégie $\pi$ afin d'atteindre son objectif (c'est-à-dire combien il bien pour l'agent d'être dans cet état). Un agent qui souhaite apprendre une stratégie doit suivre un certain "bon sens" et le MDP.

Reprenons l'exemple du "Frozen Lake" et imaginons l'agent dans sur l'état 10. Il doit juger quel est l'état le plus intéressant : 6, 9, 14 ou peut-être 11 ? Souvenez-vous que l'agent doit maximiser son gain. La question qu'on peut se poser est donc de savoir comment l'agent peut l'estimer ? C'est le but de la fonction valeur d'état, qui définit la valeur d'un état $s$ lorsque l'agent suit une stratégie $\pi$.

Nous avons déjà évoqué la notion de revenu (ou de gain global) comme étant une somme pondérée des récompenses obtenues suites aux actions prises par l'agent. L'idée est donc de faire intervenir cette notion.

On peut définir la fonction valeur d'état (state-value function) comme étant la moyenne du gain global obtenu à l'instant $t$, sachant que l'agent se trouve sur l'état $s$ et qu'il suit la stratégie $\pi$ :

$${V_\pi }\left( s \right) = E\left[ {{G_t}|{S_t} = s} \right]$$

Avec:

$${G_t} = {r_1} + \gamma {r_2} + {\gamma ^2}{r_3} + ... + {\gamma ^T}{r_T} = \sum\limits_{t = 1}^T {{\gamma ^{t - 1}}{r_t}} \quad avec \quad 0 \le \gamma \le 1$$

Exemple

La figure ci-dessous montre une grille rectangulaire qui représente un MDP avec un nombre d'états fini. Les cellules de la grille correspondent aux états de l'environnement. Sur chaque cellule, quatre actions sont possibles : haut, bas, droite et gauche. Les transitions sont déterministes. Les actions qui amènent l'agent hors de la grille le laisse dans le même état et lui donnent une récompense de -1. Les autres actions donnent une récompense de 0, sauf celles qui amène l'agent hors des états spéciaux A et B. Depuis l'état A, toutes les actions donnent une récompense de +10 et amènent l'agent sur l'état A'. Depuis l'état B, toutes les actions donnent une récompense de +5 et amènent l'agent sur l'état B'.

La grille des valeurs d'état est obtenue avec un facteur de remise $\gamma=0.9$ en suivant une stratégie aléatoire. On remarque les valeurs négatives des valeurs d'état en bas de la grille qui sont le résultat d'une forte probabilité de heurter les bords.

L'état A est celui qui possède la plus haute valeur dans le cadre de cette stratégie, mais son revenu moyen estimé est inférieur à 10 (plus petit que la récompense immédiate) car en passant par A l'agent est emmené sur A' qui est un état avec une valeur d'état négative (car depuis cet état, l'agent peut éventuellement heurter les bords et obtenir des récompenses négatives).

L'état B au contraire a une valeur supérieure à 5 (plus grande que sa récompense immédiate) car si l'agent est sur B alors il est emmené sur B', qui est un état avec une valeur d'état positive. Depuis l'état B', les pénalités estimées (récompenses négatives) qui peuvent intervenir en atteignant les bords sont compensées par le fait de pouvoir revenir facilement vers les états A et B.

3. Fonction valeur d'action (Action value function)

La fonction de valeur d'état aide l'agent à distinguer les valeurs de chaque état dans son environnement, mais ne lui permet pas de choisir une action optimale. En plus de devoir être capable d'estimer la valeur d'un état, l'agent doit donc également être capable de prendre la bonne action $a$ sur l'état $s$ lorsqu'il suit la stratégie $\pi$.

C'est le but de la fonction valeur d'action. Elle permet de quantifier de combien il est bénéfique pour un agent qui se trouve dans un état $s$ et qui suit une stratégie $\pi$, de prendre une action $a$. Cette fonction est également appelée Q-function.

De manière similaire à la fonction de valeur d'état, on définit la fonction valeur d'action comme étant la valeur moyenne du revenu obtenu à l'instant $t$ lorsque l'agent se trouve sur l'état $s$ et prend l'action $a$ et qu'il suit la stratégie $\pi$:

$${q_\pi }\left( {s,a} \right) = {E_\pi }\left[ {{G_t}|{S_t} = s,{A_t} = a} \right]$$